//
//  YTQueue.swift
//  swift_algorithm
//
//  Created by master on 2022/5/12.
//

import Foundation

public struct YTQueue<T> { //队列的特点是先进先出
    fileprivate var array = [T]() //用数组来存储数据
    
    public var isEmpty: Bool { //队列是否为空
        array.isEmpty
    }
    
    public var count: Int { //数组已存放数据
        array.count
    }
    
    public mutating func enqueue(_ element: T) { //进入队列
        array.append(element)
    }
    
    public mutating func dequeue() -> T? { //出队列
        if isEmpty { //因为是使用array.removeFirst()移除第一个元素，需要判断是否有元素可以移除
            return nil
        }else{
            return array.removeFirst()
        }
    }
    
    public var front: T? { //队头元素
        array.first
    }
    
}

//因为队列删除头元素的时候，后面的元素都要向前移动，导致效率出现问题，优化之后让元素不再移动，而是让队头标志往后移动
public struct STYQueue<T> {
    fileprivate var array = [T?]()
    fileprivate var head = 0 //标志队头下标，即此下标代表队列由这个位置开始
    
    public var isEmpty: Bool { //根据自己的count判断队列是否为空
        count == 0
    }
    
    public var count: Int { //数组元素不再删除，但是队头位置会改变，所以count为数组长度-队头位置
        array.count - head
    }
    
    public mutating func enqueue(_ element: T) { //队列添加元素，无修改
        array.append(element)
    }
    
    public mutating func dequeue() -> T? {//不再移除head，仅将原始head位置的元素置空，所以数组元素是T?类型
        //判断如果head位置在array.count位置，那么说明这个队列已经没有元素了
        guard head < array.count, let element = array[head] else { return nil }
        
        array[head] = nil
        head += 1
        
        let percentage = Double(head) / Double(array.count)//对头位置在已存在数组的位置
        if array.count > 50 && percentage > 0.25 { //数组长度已经50，并且队头位置已经超过1/4，就删除前面的元素
            array.removeFirst(head)
            head = 0
        }
        
        return element
    }
    
    public var front: T? {
        if isEmpty {
            return nil
        }else{
            return array[head]
        }
    }
    
}
